package com.sikhyeon.datastructure.model;

public class ThreadedBinaryTree {
    private TreeNode root;

    public ThreadedBinaryTree() {
        this.root = null;
    }

    public void insert(int value) {
        TreeNode newNode = new TreeNode(value);

        if (root == null) {
            root = newNode;
            return;
        }

        TreeNode current = root;
        TreeNode parent = null;

        while (true) {
            parent = current;

            if (value < current.getValue()) {
                if (!current.isLeftThread()) {
                    current = current.getLeft();
                } else {
                    break;
                }
            } else {
                if (!current.isRightThread()) {
                    current = current.getRight();
                } else {
                    break;
                }
            }
        }

        if (value < parent.getValue()) {
            newNode.setLeft(parent.getLeft());
            newNode.setRight(parent);
            parent.setLeftThread(false);
            parent.setLeft(newNode);
        } else {
            newNode.setLeft(parent);
            newNode.setRight(parent.getRight());
            parent.setRightThread(false);
            parent.setRight(newNode);
        }

        // 새 노드의 왼쪽 스레드 설정
        if (newNode.getLeft() != null && newNode.getLeft().isRightThread()) {
            newNode.getLeft().setRight(newNode);
        }

        // 새 노드의 오른쪽 스레드 설정
        if (newNode.getRight() != null && newNode.getRight().isLeftThread()) {
            newNode.getRight().setLeft(newNode);
        }
    }

    public TreeNode getRoot() {
        return root;
    }

    // 중위 순회를 위한 다음 노드
    public TreeNode inOrderSuccessor(TreeNode node) {
        if (node.isRightThread()) return node.getRight();
        node = node.getRight();
        while (!node.isLeftThread()) node = node.getLeft();
        return node;
    }
}
